package com.Oct_Ten;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * 剑指 Offer II 104. 排列的数目
 * 给定一个由 不同 正整数组成的数组 nums ，和一个目标整数 target 。请从 nums 中找出并返回总和为 target 的元素组合的个数。数组中的数字可以在一次排列中出现任意次，但是顺序不同的序列被视作不同的组合。
 *
 * 题目数据保证答案符合 32 位整数范围。
 *
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/D0F0SV
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * 2022/10/10 16:02
 */

public class Solution104 {

    /**
     * 记忆化回溯,用数组进行标记，进行了回溯算法
     *
     */

    public int combinationSum4(int[] nums, int target) {
        //Arrays.sort(nums);
        int[] mem=new int[target+1];
        Arrays.fill(mem,-1);
        return dfs(nums,target,mem);
        //return mem[nums.length];
    }

    int dfs(int[] nums,int target,int[] mem){
        if (target<=0)
        {
            if (target==0) return 1;
            else return 0;
        }
        if (mem[target]!=-1)
        {
            return mem[target];
        }
        mem[target]=0;
        for (int num : nums) {
            mem[target] += dfs(nums, target - num, mem);
        }
        return mem[target];
    }

//    void dfs(int[] nums,int target,int sum){
//        if (sum==target)
//        {
//            cnt++;
//        }
//        for (int i=0;i<nums.length&&sum+nums[i]<=target;i++)
//        {
//            dfs(nums,target,sum+nums[i]);
//        }
//    }

    public static void main(String[] args) {
        Solution104 solution104=new Solution104();
        System.out.println(solution104.combinationSum4(new int[]{3,1,2,4},4));
    }
}
